import collections
import functools

class Solution(object):
    def Leetcode(self, words):
        target = (1, 4, 3, 1, 2, 1, 1)
        total = [0, 0, 0, 0, 0, 0, 0]
        n = len(words)
        d = {'h': 0, 'e': 1, 'l': 2, 'c': 3, 'o': 4, 't': 5, 'd': 6}
        for word in words:
            for c in word:
                if c in d:
                    total[d[c]] += 1
        for i in range(7):
            if total[i] < target[i]:
                return -1

        def find(word):
            m = len(word)
            @functools.cache
            def dfs(val):
                if val == 0:
                    return 0
                total_count = 0
                for j in range(m):
                    if (val >> j) & 1 and word[j] not in d:
                        return float('inf')
                    if (val >> j) & 1 == 0:
                        total_count += 1
                left_count = 0
                min_cost = float('inf')
                for j in range(m):
                    if (val >> j) & 1 == 0:
                        left_count += 1
                    if (val >> j) & 1:
                        last_val = val ^ (1 << j)
                        cost = left_count * (total_count - left_count)
                        min_cost = min(min_cost, cost + dfs(last_val))
                return min_cost
            out = {}
            for val in range(1, 1 << m):
                ans = dfs(val)
                if ans < float('inf'):
                    now_out = [0] * 7
                    for j in range(m):
                        if (val >> j) & 1:
                            now_out[d[word[j]]] += 1
                    temp = tuple(now_out)
                    flag = True
                    for j in range(7):
                        if temp[j] > target[j]:
                            flag = False
                            break
                    if flag:
                        if temp not in out:
                            out[temp] = ans
                        else:
                            out[temp] = min(ans, out[temp])
            return out
        st = {tuple([0] * 7): 0}
        for word in words:
            next_st = collections.defaultdict(lambda: float('inf'))
            out = find(word)
            if out:
                for node in st:
                    next_st[node] = min(next_st[node], st[node])
                    for a in out:
                        next_cost = out[a] + st[node]
                        next_state = list(node)
                        flag = True
                        for j in range(7):
                            next_state[j] += a[j]
                            if next_state[j] > target[j]:
                                flag = False
                                break
                        if flag:
                            tuple_state = tuple(next_state)
                            next_st[tuple_state] = min(next_st[tuple_state], next_cost)
                st = next_st
        ans = float('inf')
        for node in st:
            if node == target:
                ans = min(ans, st[node])
        return ans







data = Solution()
words = ["hold", "engineer", "cost", "level"]
print(data.Leetcode(words))
